Conventional data storage systems may include one or more data storage devices (e.g. disk drives) connected to a controller or manager. A logical volume manager (also called a logical disk manager) can be used to manage systems containing multiple data storage devices. The logical volume manager configures a pool of storage devices into logical volumes so that applications and users interface with logical volumes instead of directly accessing physical media. The logical volume manager divides each storage device into one or more partitions. Each partition can, and typically does, have a different length. When a logical volume is no longer needed, its partitions are deleted so that space on the disk drives is made available for another partition to be created. However if a new partition is larger than the available space, then the space cannot be reused for the new partition. If the new partition is smaller than the available space, then a portion of the free space will be used and an even smaller piece will remain free. Over time, this results in many small pieces of free space that cannot be reused. This problem is often referred to as “fragmentation.”
U.S. Pat. No. 6,405,284 granted to Bridge on Jun. 11, 2002, and entitled “Distributing data across multiple data storage devices in a data storage system” is incorporated by reference herein in its entirety. This patent describes an invention, in which, one feature of one embodiment is to divide each disk drive into many small fixed size pieces. During normal operation, storage space on a disk drive is allocated and freed in units of the fixed size pieces. Fragmentation is reduced or eliminated because all pieces are the same size. Another feature described in this patent is that each logical volume is made of pieces from many disk drives. The pieces of a logical volume are spread out as evenly as is practical so that two pieces on the same disk drive are far apart in the address space of the logical volume. Thus I/O load is spread evenly over all disk drives.
Prior art methods of allocating the pieces to disk drives (hereinafter, simply “disks”) have certain disadvantages. For example, if pieces are allocated to disks in a round-robin fashion, then disks that are smaller run out of space faster than larger disks. In the following example, assume there are four disks, consisting of two disks D1 and D2 of 200 MB each and two disks D3 and D4 of 100 MB each. If one were to use round-robin scheme to allocate eight pieces (of 50 MB each), then the distribution results as shown in FIG. 1 and in the following table (wherein X1-X8 are the labels of the eight pieces).
D1D2D3D4X1X2X3X4X5X6X7X8AVAILABLEAVAILABLEN/AN/AAVAILABLEAVAILABLEN/AN/AIn the above table, D1 and D2 have space available whereas D3 and D4 do not have any available space (denoted as “N/A” because these disks are smaller). Therefore, the round-robin allocation causes D3 and D4 to become full although D1 and D2 are only half full.
Another method (called “sequential proportional”) computes a weight for each disk, as the ratio of each individual disk's capacity divided by the total storage capacity of all disks. In the above-described example, the weights are as follows:
D1D2D3D41/31/31/61/6Next, the weights are multiplied by the total number of pieces, to decide how many pieces are to be allocated to each disk. So if there are twelve pieces of 25 MB each that are to be allocated, then D1 receives four pieces (X1-X4), D2 receives four pieces (X5-X8), D3 receives two pieces (X9, X10) and D4 receives two pieces (X11, X12) as follows.
D1D2D3D4X1X5X9 X11X2X6X10X12X3X7N/AN/AX4X8N/AN/AThe above distribution is more uniform across the disks because all disks become full at about the same time. But this method has the problem that when data is being accessed from the first disk D1, the remaining disks D2-D4 are kept idle which results in lower throughput than possible (if all disks were being accessed in parallel). Another problem with this method (as well as the round robin scheme) is that if a disk were to be dropped (e.g. if disk D4 is to be removed), then movement of D4's pieces to one of the remaining disks can result in an uneven distribution (wherein some disks have many more pieces than other disks). Hence an improved method for allocating pieces to disks will be useful.